package com.linyaonan.leetcode.easy._2864;

/**
 *
 * 给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
 *
 * 你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
 *
 * 以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
 *
 * 注意 返回的结果字符串 可以 含前导零。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "010"
 * 输出："001"
 * 解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。
 * 示例 2：
 *
 * 输入：s = "0101"
 * 输出："1001"
 * 解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 100
 * s 仅由 '0' 和 '1' 组成
 * s 中至少包含一个 '1'
 *
 * @author: Lin
 * @date: 2024/3/13
 */
public class MaximumOddBinaryNumber {

    /**
     * 找出有多少1，多少0,只保留一个1在结尾，剩余的全部放到开头
     * @param s
     * @return
     */
    public String maximumOddBinaryNumber(String s) {
        int oCount = 0;
        int zCount = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                oCount++;
            } else {
                zCount++;
            }
        }
        // 预留一个1在最后
        oCount--;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < oCount; i++) {
            sb.append("1");
        }
        for (int i = 0; i < zCount; i++) {
            sb.append("0");
        }

        sb.append("1");

        return sb.toString();

    }

    /**
     * 返回最大数值
     * @param s
     * @return
     */
    public long maximumOddBinaryLong(String s) {
        int oCount = 0;
        int zCount = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                oCount++;
            } else {
                zCount++;
            }
        }
        // 预留一个1在最后
        oCount--;
        long p = 0L;
        for (int i = 0; i < oCount; i++) {
            p += (1 << i);
        }
        return (p << zCount + 1) + 1;
    }

}
